Permutations

Time: O(NxN!); Space: O(N); medium

Given a collection of distinct integers, return all possible permutations.

Example 1:

Input: nums = [1,2,3]

Output:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

1. Recurson

[4]:

class Solution1(object):
    """
    Time: O(N*N!)
    Space: O(N)
    """
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        used = [False] * len(nums)
        self.permuteRecu(result, used, [], nums)
        return result

    def permuteRecu(self, result, used, cur, nums):
        if len(cur) == len(nums):
            result.append(cur[:])
            return

        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                cur.append(nums[i])
                self.permuteRecu(result, used, cur, nums)
                cur.pop()
                used[i] = False

[5]:

s = Solution1()
nums =  [1,2,3]
assert s.permute(nums) == [
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

2. Recursion + DFS

[6]:

class Solution2(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(nums, [], res)
        return res

    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)

        for i in range(len(nums)):
            # e.g., [1, 2, 3]: 3! = 6 cases
            # idx -> nums, path
            # 0 -> [2, 3], [1] -> 0: [3], [1, 2] -> [], [1, 2, 3]
            #                  -> 1: [2], [1, 3] -> [], [1, 3, 2]
            #
            # 1 -> [1, 3], [2] -> 0: [3], [2, 1] -> [], [2, 1, 3]
            #                  -> 1: [1], [2, 3] -> [], [2, 3, 1]
            #
            # 2 -> [1, 2], [3] -> 0: [2], [3, 1] -> [], [3, 1, 2]
            #                  -> 1: [1], [3, 2] -> [], [3, 2, 1]
            self.dfs(nums[:i] + nums[i+1:], path + [nums[i]], res)

[7]:

s = Solution2()
nums =  [1,2,3]
assert s.permute(nums) == [
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]